/**
 * 移动零
 *
 * 给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
 * 请注意 ，必须在不复制数组的情况下原地对数组进行操作。
 *
 * 示例 1:
 * 输入: nums = [0,1,0,3,12]
 * 输出: [1,3,12,0,0]
 *
 * 示例 2:
 * 输入: nums = [0]
 * 输出: [0]
 *
 * 提示:
 * 1 <= nums.length <= 104
 * -231 <= nums[i] <= 231 - 1
 *
 * 进阶：你能尽量减少完成的操作次数吗？
 */

/**
 * 这里就是利用双指针, 当我们遇到的不是 0 的时候, 将它
 * 移动到前面来, 所以我们前面要用一个标志, 标记一下 0
 * 和 不是 0 的分界点, 每当遇到 不是 0, 就将它移动到
 * 这个标志, 然后使这个标志++, 成功了
 * 时间复杂度 : O(n)
 * 空间复杂度 : O(1)
 */

public class Main {
    public void moveZeroes(int[] nums) {
        int n = nums.length;

        // 分界点     目前为止
        int cur = 0, dest = 0;
        while (dest < n) {

            // 遇到不是 0, 就将它移动到前面来
            if (nums[dest] != 0) {
                int tmp = nums[cur];
                nums[cur] = nums[dest];
                nums[dest] = tmp;
                cur++;
            }
            dest++;
        }
    }

    public static void main(String[] args) {
        Main test = new Main();
        int[] nums = new int[]{0,1,0,3,12};
        test.moveZeroes(nums);
    }
}